package review.Day_0411;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zxc
 * @date 2023/04/11 22:04
 **/

public class Solution01 {
    // 递归实现前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderDFS(root , result);
        return result;
    }
    // 深度优先遍历
    private void preorderDFS(TreeNode root, List<Integer> result) {
        if(root == null){
            return;
        }
        result.add(root.val);
        preorderDFS(root.leftNode , result);
        preorderDFS(root.rightNode , result);
    }

    // 递归中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderDFS(root , result);
        return result;
    }

    private void inorderDFS(TreeNode root, List<Integer> result) {
        if(root == null){
            return;
        }
        inorderDFS(root.leftNode , result);
        result.add(root.val); // 即，中序遍历只需要将根节点加入时机，是遍历完当前根节点的左子树后;
        inorderDFS(root.rightNode , result);
    }

    // 递归实现后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderDFS(root , result);
        return result;
    }

    private void postorderDFS(TreeNode root, List<Integer> result) {
        if(root == null){
            return;
        }
        postorderDFS(root.leftNode , result);
        postorderDFS(root.rightNode , result);
        result.add(root.val); // 即，后序遍历只需要将根节点加入时机，是遍历完当前根节点的左子树 && 遍历完当前根节点的右子树后;
    }

}
